1. Field of the Invention
This invention relates to digital computers, particularly to digital computers having memory devices for storing information in individually adressable locations, and more particularly to methods of accessing particular locations within such memory devices.
2. Description of the Prior Art
A stored-program computer typically includes a device for storing the memory address, or the equivalent thereof, of the next instruction to be executed by the central processing unit; this device usually takes the form of a register, and is typically called the "program counter", or "PC". The program counter typically is loaded with the starting address of a desired sequence of instructions, and is incremented from that point to "point to" successive addresses of the subsequent instructions.
The next instruction to be executed is typically the next sequential instruction in the memory device. However, some of the instructions may be "branch" or "jump" instructions, which result in next executing an instruction other than the next sequential instruction. Such other instruction is known as the "target" instruction of a branch.
A "conditional branch" instruction specifies that a target instruction (other than the next sequential instruction) will be executed if a certain specified condition (such as a machine-state condition or a variable being equal to a certain value) is met. If the specified condition is not met, the next sequential instruction is executed.
In a rudimentary digital computer, an instruction to be executed is fetched from the memory location indicated by the program counter. The program counter is then incremented to point to the next sequential instructions to be fetched. If execution of the current instruction indicates that branching is to occur, the program counter contents are overwritten by the branch address specified by the current branch instruction. Using the program counter to indicate the address in memory of the next instruction, the correct next instruction is then fetched.
Another situation in which instructions are executed in an order other than that in which they are arranged in memory occurs in conjunction with subroutine calls and returns. Instruction subsequences that may be needed repeatedly may be written as "subroutines". Then, when it is desired to execute one such subsequence, a "CALL" instruction appears in the instruction sequence; the call instruction specifies the starting address of the subroutine as the instruction to be executed next. The last instruction in the subroutine is a "RETURN" instruction, which indicates that the subroutine has run to completion and that the sequence which called the subroutine is now to be resumed at the instruction immediately following the CALL instruction (the instruction which invoked the subroutine).
To facilitate call and return instructions, computers typically employ a LIFO (last-in, first-out) memory, usually called a "stack", to store return addresses (i.e., the addresses of instructions following call instructions, which are the addresses at which execution is to be resumed after executing return instructions). While executing a call instruction, the program counter contains the address of the next sequential instruction, having been incremented as mentioned above after being used to fetch the call instruction. The program counter contents are then usually placed in the next available location in the stack (often referred to as the "top of the stack"). The program counter is loaded with the address specified in the call instruction as the starting address of the subroutine, and execution of the subroutine proceeds from there. When the return instruction is encountered, the program counter is loaded with the address of the instruction at which execution is to be resumed, i.e. the address of the instruction following the call instruction which invoked the subroutine. This address is found on top of the stack, for it was placed there as part of the execution of the call instruction.
Associated with the stack is a "stack pointer", typically a multibit register with provision for incrementing and decrementing by one. A register containing the address of some item is commonly said to "point to" that item. The stack pointer initially points to the first location in the stack, is incremented by one whenever anything is placed on the stack, and is decremented by one whenever anything is retrieved from the stack. Thus, the stack pointer always points to the next available location in the stack. This scheme allows for "nested subroutine calls", i.e., for a subroutine to call another subroutine. If, for example, an instruction sequence has called subroutine A which has called subroutine B, then when subroutine B encounters a return instruction, the address to which it is to return in subroutine A is retrieved from the top of the stack, and the stack pointer is decremented by one; when subroutine A encounters a return instruction, the address to which it is to return in the main sequence is retrieved from the "new" top of the stack, the locations to which the stack pointer has been decremented to point. Calls may be nested over as many levels as there are available locations in the stack.
The stack portions of prior art machines typically hold the address of the next memory location to be accessed in the stack. For each memory access, the contents of the stack pointer must be decoded (usually accomplished by gating logic) to select the corresponding memory location. Additional gating must be employed to determine whether the stack has overflowed (i.e., an attempt was made to exceed its capacity) or underflowed (i.e., an attempt was made to retrieve non-existent contents).
Throughout this document, the term "branching" will be used to denote the situation that exists when the next instruction to be executed is other than the next sequential one, regardless of whether this is because of a branch instruction, a call instruction, or a return instruction.
Efforts to speed up the operation of digital computers have included such improvements as "instruction prefetching", wherein the next instruction to be executed is fetched from memory while a current instruction is still executing. Thus, execution of an instruction can commence immediately upon the completion of the execution of the previous instruction and the central processing unit is not delayed while memory accesses, bus transfers, and the like take place.
A problem in extracting the full benefit from instruction prefetching occurs in conjunction with conditional branch instructions. It usually cannot be known whether a conditional branch is to take place until some point near the end of execution of the conditional branch instruction, by which time the next sequential instruction (not the target instruction) should already have been fetched. A delay then ensues while fetching the target instruction. Various approaches have been tried to limit this delay in fetching the target instruction, such as mechanisms for predicting the outcome of a conditional branch (see, for example, U.S. Pat. No. 4,430,706 issued to Sand), or assuming that conditional branches will always be taken (or never be taken), and requiring the programmer to construct his programs in as close conformance as possible to the assumption. (For example, in coding a loop that is to be executed twenty times, the programmer can employ an exit branch that is not taken twenty times and then taken once or alternatively a return branch that is taken twenty times and then not taken once.)
Despite these various approaches, the prediction or assumption is not always correct--the wrong instruction has been prefetched, and a delay ensues while fetching the correct next instruction.